//
// Created by yanhai on 2021/1/15.
//

// B树

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int KEY_TYPE;

#define IS_LEFT 1


typedef struct btree_node_ {
    KEY_TYPE *keys; // key数组
    struct btree_node_ **childrens; // 孩子数组
    int num;    // 孩子的个数
    int leaf;   // 是否是叶子节点
} btree_node;

typedef struct btree_ {
    btree_node *root;
    int t;  //  树的阶
} btree;

/**
 * 创建一个node节点
 * @param t 数的度
 * @param leaf 是否是叶子节点
 * @return
 */
btree_node *btree_node_create(int t, int leaf) {
    btree_node *node = (btree_node *) calloc(1, sizeof(btree_node));
    assert(node != NULL);

    node->leaf = leaf;
    node->keys = (KEY_TYPE *) calloc(1, (2 * t - 1) * sizeof(KEY_TYPE));
    assert(node->keys != NULL);
    node->childrens = (btree_node **) calloc(1, (2 * t) * sizeof(btree_node));
    assert(node->childrens != NULL);
    node->num = 0;

    return node;
}

/**
 * 释放node节点
 * @param node
 */
void btree_node_destroy(btree_node *node) {
    if (node) {
        free(node->childrens);
        free(node->keys);
        free(node);
    }
}

/**
 * 创建一棵B树
 * @param T
 * @param t 树的度
 */
void btree_create(btree *T, int t) {
    T->t = t;
    T->root = btree_node_create(t, IS_LEFT);
}

void btree_split_child(btree *T, btree_node *x, int i) {
    int t = T->t;

    btree_node *y = x->childrens[i];
    btree_node *z = btree_node_create(t, y->leaf);

    z->num = t - 1;

    int j = 0;
    for (j = 0; j < t - 1; j++) {
        z->keys[j] = y->keys[j + t];
    }
    if (y->leaf == 0) {
        for (j = 0; j < t; j++) {
            z->childrens[j] = y->childrens[j + t];
        }
    }

    y->num = t - 1;
    for (j = x->num; j >= i + 1; j--) {
        x->childrens[j + 1] = x->childrens[j];
    }

    x->childrens[i + 1] = z;

    for (j = x->num - 1; j >= i; j--) {
        x->keys[j + 1] = x->keys[j];
    }
    x->keys[i] = y->keys[t - 1];
    x->num += 1;
}

void btree_insert_nonfull(btree *T, btree_node *x, KEY_TYPE k) {

    int i = x->num - 1;

    if (x->leaf == 1) {

        while (i >= 0 && x->keys[i] > k) {
            x->keys[i + 1] = x->keys[i];
            i--;
        }
        x->keys[i + 1] = k;
        x->num += 1;

    } else {
        while (i >= 0 && x->keys[i] > k) i--;

        if (x->childrens[i + 1]->num == (2 * (T->t)) - 1) {
            btree_split_child(T, x, i + 1);
            if (k > x->keys[i + 1]) i++;
        }

        btree_insert_nonfull(T, x->childrens[i + 1], k);
    }
}

void btree_insert(btree *T, KEY_TYPE key) {
    //int t = T->t;

    btree_node *r = T->root;
    if (r->num == 2 * T->t - 1) {

        btree_node *node = btree_node_create(T->t, 0);
        T->root = node;

        node->childrens[0] = r;

        btree_split_child(T, node, 0);

        int i = 0;
        if (node->keys[0] < key) i++;
        btree_insert_nonfull(T, node->childrens[i], key);

    } else {
        btree_insert_nonfull(T, r, key);
    }
}


/**
 * 打印以node中第layer个孩子为根的B树
 * @param T
 * @param node
 * @param layer
 */
void btree_node_print(btree *T, btree_node *node, int layer) {
    btree_node *p = node;

    if (p) {
        printf("\nlayer=%d, keynum=%d, is_leaf=%d\n", layer, p->num, p->leaf);

        for (int i = 0; i < node->num; ++i) {
            printf("%c ", p->keys[i]);
        }
        printf("\n");

        layer++;
        for (int i = 0; i < p->num; ++i) {
            if (p->childrens[i]) {
                btree_node_print(T, p->childrens[i], layer);
            }
        }
    } else {
        printf("the tree is empty\n");
    }
}

/**
 * B树的遍历打印
 */
void btree_print(btree *T) {
    btree_node_print(T, T->root, 0);
}

int main() {

    btree T = {0};

    btree_create(&T, 3);

    // insert
    char key[26] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for (int i = 0; i < 26; i++) {
        btree_insert(&T, key[i]);
    }

    btree_print(&T);

    return 0;
}
